#define _CRT_SECURE_NO_WARNINGS 1

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
#include <cstddef>
#include <list>
#include <ratio>
class Solution {
public:
	void Create(TreeNode* node, TreeNode*& ptail)
	{
		if (node->left != nullptr)
		{
			Create(node->left, ptail);
		}
		ptail->right = node;
		node->left = ptail;
		ptail = ptail->right;
		if (node->right != nullptr)
		{
			Create(node->right, ptail);
		}
	}
	TreeNode* Convert(TreeNode* pRootOfTree) {
		if (pRootOfTree == nullptr) return nullptr;
		TreeNode* head = new TreeNode(1);
		TreeNode* ptail = head;
		Create(pRootOfTree, ptail);
		ptail = head;
		head = head->right;
		head->left = nullptr;
		delete ptail;
		return head;
	}
};
